package formal.tree.bst;

import java.util.ArrayList;
import java.util.List;

/**
 * @author DengYuan2
 * @create 2021-01-25 20:50
 */
public class E_653 {
    public static void main(String[] args) {
        Integer[] a = {5, 3, 6, 2, 4, null, 7};
        TreeNode treeNode = TreeNode.generateTree(a);
        boolean res = findTarget2(treeNode, 11);
        System.out.println(res);

    }

    /**
     * 我的写法-中序遍历，将所有值放入数组，再找数组里是否有和
     * @param root
     * @param k
     * @return
     */
    public static boolean findTarget(TreeNode root, int k) {
        if (root == null) {
            return false;
        }
        List<Integer> list = new ArrayList<>();
        inOrder(root,list);
        for (int i = 0; i < list.size(); i++) {
            for (int j = list.size()-1; j >i ; j--) {
                if (list.get(i)+list.get(j)==k){
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 官方/大神的写法-同样的思路-更为简单啊！
     * @param root
     * @param k
     * @return
     */
    public static boolean findTarget2(TreeNode root,int k){
        if (root==null){
            return false;
        }
        List<Integer> list = new ArrayList<>();
        inOrder(root,list);
        //区别如下：
        int i = 0,j = list.size()-1;
        while (i<j){
            int sum = list.get(i)+list.get(j);
            if (sum==k){
                return true;
            }else if (sum<k){
                i++;
            }else {
                j--;
            }
        }
        return false;
    }

    public static void inOrder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        inOrder(root.left, list);
        list.add(root.val);
        inOrder(root.right, list);
    }
}
